1. Field of the Invention
The present invention relates generally to optical character readers, and more particularly to a neural network processing apparatus in an optical character reader for identifying unknown image patterns.
2. Description of the Background
Recently, unknown image patterns have been processed by association in a neural network. The neural network is comprised of a plurality of discrete processing modules, or "neurons." Inputs of each neuron are linked to the outputs of other neurons of the network, such that the signals between neurons are conditioned by weighting factors (weights). Each neuron processes an input signal according to a predetermined transfer function to produce an output signal.
The Hopfield model is a well-known example of a neural network. In the Hopfield model, an output value of a neuron is calculated from the output values of other interconnected neurons and corresponding weights between the neurons. The output value of a neuron is then supplied to the interconnected other neurons. The Hopfield model is represented as follows: EQU V.sub.j =f(u.sub.j) (1) EQU u.sub.j =.delta..sub.uj +(1-.delta.) (.sub.i .SIGMA.T.sub.ji V.sub.i I.sub.j) (2) Z
where:
V.sub.j =output value of neuron j
u.sub.j =input value of neuron j
f=a monotonic increment function having a maximum and a minimum
.delta.=inertial constant (0&lt;.delta.&lt;1)
T.sub.ji =weight between neuron i and neuron j
I.sub.j =threshold of neuron j (a constant value)
The formulae (1) and (2) represent that output value V.sub.j of neuron j is calculated by multiplication of output value V.sub.i of neuron i and weight T.sub.ji, subtraction of I.sub.j from the sum of the multiplication, and operation of the function f upon the subtraction. If the output value of the neuron changes, the output values of other interconnected neurons change. Therefore, to calculate the final output value of the neuron, the calculation of the formulae (1) and (2) is repeated for all neurons until the output values of all neurons become unchanging.
Next, an example for identifying unknown image patterns by the Hopfield model is explained. FIG. 1 shows six kinds of image patterns, which consists of three continuous black pixels ("1") and three continuous white pixels ("-1"). This set of image patterns, referred to as instruction image patterns, constitutes the set of possible image patterns from which an unknown image pattern can be identified.
In performing a character recognition operation, it is often the case that a portion of an image pattern is missing, blurred, or indistinct. Such image pattern constitutes an unknown image pattern. An example of an unknown image pattern is shown in FIG. 5. If discrete portions (pixels) of an unknown image pattern are each associated with one neuron, the set of output values of all neurons in the network can be used to identify the associated unknown image.
A neural network containing six neurons, each corresponding to one of the six pixels of the instruction image patterns, is shown in FIG. 2. In this case, the output value of each neuron associated with a black pixel is "1", and the output value of each neuron associated with a white pixel is "-1". If two neurons associated with the instruction patterns have a tendency to generate the same output value simultaneously, the neural network is configured such that a positive weight is set between the two neurons. If two neurons have tendency to generate different output values simultaneously, the neural network is configured such that a negative weight is set between the two neurons.
FIG. 3 shows a neural network configured to identify unknown image patterns consisting of one of the instruction patterns of FIG. 1. In FIG. 3, absolute values of weights between two opposite neurons are larger than the absolute values of weights between two neighboring neurons. The reason for this is that the probability for two opposite neurons of the instruction patterns of FIG. 1 to generate different values (black and white) is larger than the probability for two neighboring neurons of the instruction patterns of FIG. 1 to generate same values (black or white).
The monotonic increment function may consist of the hyperbolic function "tanh" whose limit is (-1,1) as shown in FIG. 4. (I.sub.j =0) In this case, the association of one of the instruction image patterns with an unknown image pattern, having two undetermined pixels, is explained.
For example neurons 0, 1, 2, 3, 4, 5 of FIG. 3 having respective output values of V.sub.0, V.sub.1, V.sub.2, V.sub.3, V.sub.4, V.sub.5, are associated with pixels of the unknown image pattern of FIG. 5 as follows: EQU (V.sub.0, V.sub.1, V.sub.2, V.sub.3, V.sub.4, V.sub.5)=(unknown, 1, 1, -1, -1, unknown)
To associate the output value of neurons 0 and 5, the following steps are processed.
1. The determined values (V.sub.1 -V.sub.4) are assigned to the output values of the neurons (1-4) as initial values, and the output values of the neurons (0 and 5) are initially set to "0".
2. The calculation of formulae (1) and (2) is performed for all neurons. As a result of these calculations, the values V.sub.0 . . . V.sub.5 change from initial values to new values.
3. The calculation of formula (1) and (2) is again performed for all neurons, using as input values the new output values obtained in step 2.
4. The calculation of the formulae (1) and (2) is repeatedly performed for all neurons, using as input values the output values obtained by the previous calculation until the output values of all neurons become unchanging.
The set of output values of the neurons of FIG. 3, which are unchanging, correspond to the pixels of the pattern of FIG. 5 and constitute an identification of the unknown image pattern. If the output value of a neuron, which is unchanging, is positive value, the corresponding pixel is black. If the output value of neuron, which is unchanging, is negative value, the corresponding pixel is white. In this example, the output value V.sub.0 is "1" and V.sub.5 is "-1", and the unknown image is identified as pattern 1 in FIG. 1.
As the noted above, the method for identifying binary image patterns (black and white) by using the neural network is known. However, a method for identifying multivalued image patterns (images formed of grayscale pixels including black and white) has not been developed. In the prior art, the output value of a neuron is desired to be maximum ("1") or minimum ("-1") and it is not desired to be distributed gradually from maximum to minimum.
The distribution of the output value of a neuron depends on the transfer function f. As for change of the distribution of the output according to the gain .lambda. of the monotonic function f(X), the function can be represented as follows. ##EQU1## The formula (3) indicates that if the input value X is from "-1" to "1", the function f(X) shows a linear characteristic of slope .lambda.. If the output value is above "1", the function f(X) is saturated with "1". If the output value is below "-1", the function f(X) is saturated with "-1". As shown in FIG. 6, the larger the value of .lambda. is, the larger is the slope of f(X) in the vicinity of X=0. The smaller the value of .lambda. is, the smaller is the slope of f(X) in the vicinity of X=O. In short, if the value of .lambda. is large, the distribution of the output value of the neurons is biased to maximum and minimum. If the value of .lambda. is small, the distribution of the output value of the neurons is biased to nearly "0". Accordingly, to associate a multivalued image pattern correctly, the value of .lambda. must be controlled dynamically in order to insure that the output values of the neurons at steady state correctly identify an unknown multivalued pattern. However, in the prior art, such control method has not been developed.